import java.util.*;

public  class Binarytree {
     static class TreeNode {
         public char val;
         public TreeNode left;//存储左孩子的引用
         public TreeNode right;//存储右孩子的引用

         public TreeNode(char val) {
             this.val = val;
         }
     }

     public TreeNode createTree() {
         TreeNode A = new TreeNode('A');
         TreeNode B = new TreeNode('B');
         TreeNode C = new TreeNode('C');
         TreeNode D = new TreeNode('D');
         TreeNode E = new TreeNode('E');
         TreeNode F = new TreeNode('F');
         TreeNode G = new TreeNode('G');
         TreeNode H = new TreeNode('H');

         A.left = B;
         A.right = C;
         B.left = D;
         B.right = E;
         C.left = F;
         C.right = G;
         E.right = H;
         return A;
     }

     //前序遍历
    public void preOrder(TreeNode root) {
        if(root==null) return;
        //先前序前序遍历根节点---根树---由于根树只有一个节点所以前序遍历结果就是这个节点
        System.out.print(root.val);
        //然后前序遍历左子树--左边这颗树可不敢直接打印--因为左 右树节点个数不一定是1个
        //遍历一颗树的方法我们已经有了吗??---有了preOrder方法就是专门用来前序遍历一棵树的
        preOrder(root.left);
        //最后右子树
        preOrder(root.right);
    }

    /**
     * 遍历思想
     */
    //前序遍历的结果放入集合当中
    public List<Character> ret=new ArrayList<>();
    public List<Character> preOrder1(TreeNode root) {
        if(root==null) return null;
        //先前序前序遍历根节点---根树---由于根树只有一个节点所以前序遍历结果就是这个节点
        ret.add(root.val);
        //然后前序遍历左子树--左边这颗树可不敢直接打印--因为左 右树节点个数不一定是1个
        //遍历一颗树的方法我们已经有了吗??---有了preOrder方法就是专门用来前序遍历一棵树的
        preOrder(root.left);
        //最后右子树
        preOrder(root.right);
        return ret;
    }

    /**
     * 子问题思想
     * @param root
     */
    public List<Character> preOrder2(TreeNode root) {
        List<Character> ret=new ArrayList<>();
        if(root==null) return ret;
        //先前序前序遍历根节点---根树---由于根树只有一个节点所以前序遍历结果就是这个节点
        ret.add(root.val);
        //然后前序遍历左子树--左边这颗树可不敢直接打印--因为左 右树节点个数不一定是1个
        //遍历一颗树的方法我们已经有了吗??---有了preOrder方法就是专门用来前序遍历一棵树的
        ret.addAll(preOrder2(root.left));
        //最后右子树
        ret.addAll(preOrder2(root.right));
        return  ret;
    }


    //中序遍历
    public void inOrder(TreeNode root){
         if(root==null) return;
         //先处理左子树
        inOrder(root.left);
        //在处理根
        System.out.print(root.val);
        //最后处理右子树
        inOrder(root.right);
    }
    //后续遍历
    public void postOrder(TreeNode root){
        if (root==null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
     }
     public static int size =0;
     public int size1(TreeNode root){
         if(root==null) return 0;
         return  size1(root.left)+size1(root.right)+1;
     }
     public void sizedemo(TreeNode root){
         if(root==null) return;
         size++;
         sizedemo(root.left);
         sizedemo(root.right);
     }
     public int size(TreeNode root){
         sizedemo(root);
         return size;
     }

    /**
     * 遍历思路
     * @param root
     * @return
     */
    int count=0;
    public void getLeafNodeCount(TreeNode root){
        if(root==null) return;
        if (root.left==null&&root.right==null) count++;
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }
    /**
     * 子问题思路
     */
    public int getLeafNodeCount1(TreeNode root){
        if(root==null) return 0;
        if(root.left==null&&root.right==null)  return 1;
        else return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);
    }

    /**
     * 获取第k层节点个数
     * @param root
     * @param k
     * @return
     */
   public int getKLevelNodeCount(TreeNode root,int k){
        int ret=0;
        if (root==null) return 0;
        if(k==1) return 1;
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

    // 获取二叉树的高度
   public int getHeight(TreeNode root) {
       //转换成 左子树的高度vs右子树的高度--->最大值+1
       if (root==null) return 0;
       int left=getHeight(root.left);//左子树的高度
       int right=getHeight(root.right);//右子树的高度
       int maxHeight=Math.max(left,right);
       return maxHeight+1;
    }

    // 检测值为value的元素是否存在
    /**
     * 相当于前序遍历--遍历到一个位置判断是否是val是就返回
     * @param root
     * @param val
     * @return
     */
  public TreeNode find(TreeNode root, char val){
       if(root==null) return null;
       if(root.val==val) return root;
        TreeNode leftnode=find(root.left,val);
        if(leftnode!=null) return leftnode;
        TreeNode rightnode=find(root.right,val);
        if(rightnode!=null) return rightnode;
        return null;
    }

    /**
     * 假设p树的节点数---m  q树的节点数---n
     *o(min(n,m))
     * 判断两二叉树是否是相同二叉树
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null) return true;
        if(p!=null&&q!=null){
            if(p.val!=q.val){
                return false;
            }
        }else return false;
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }

    /**
     * 判断一个树是否是一棵树的子树
     * 思路:先判断是否和整棵树相同---然后左子树相同---右子树相同
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null) return false;
        //先处理根树---判断两根树是否相同
        if(isSameTree(root,subRoot)) return true;
        //处理左子树
        boolean left=isSubtree(root.left,subRoot);
        if(left) return left;
        //处理右子树
        boolean right=isSubtree(root.right,subRoot);
        if(right) return right;
        return false;
    }

    /**
     * 翻转二叉树
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return null;
        //先翻转根
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        //翻转左子树
        invertTree(root.left);
        //翻转右子树
        invertTree(root.right);
        return root;
    }

    public boolean isBalanced(TreeNode root) {
        //左右子树高度差<=1---平衡二叉树--每个节点的左右子树也必须是平衡二叉树。
        //一棵树是由根树和子树组成,必须满足根树和子树都是平衡二叉树-->这整棵树是平衡二叉树
        if(root==null) return true;
        int leftH=getHeight(root.left);
        int rightH=getHeight(root.right);
        return Math.abs(leftH-rightH)<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }
    public boolean isBalanced1(TreeNode root) {
        //在求高度的时候就应该能够作出判断
        return getHeight1(root)>=0;
    }
    private int getHeight1(TreeNode root) {
        if(root==null) return 0;
        int leftH=getHeight1(root.left);
        int rightH=getHeight1(root.right);
        //根据左右树的高度作出判断并进行标记
        if (leftH==-1||rightH==-1||Math.abs((leftH-rightH))>1) return -1;
        else return Math.max(leftH,rightH)+1;
    }

    /**
     * 解法2
     * o()
     * @param root
     * @return
     */
    public boolean isSymmetric1(TreeNode root){
        if(root==null) return true;
        //判断一棵二叉树是否对称--->看它的左右子树是否对称--->判断两棵树是否对称
       return isSymmetricChild(root.left,root.right);
    }

    public boolean isSymmetricChild(TreeNode leftnode,TreeNode rightnode){
        //判断两颗树是否对称
        //先判断根是否一样
        if(leftnode!=null&&rightnode==null||leftnode==null&&rightnode!=null) return  false;
        if (leftnode==null&&rightnode==null) return true;
        if(leftnode.val!=rightnode.val) return false;
        //根已经相等
        //判断左右子树
        return isSymmetricChild(leftnode.left,rightnode.right)&&isSymmetricChild(leftnode.right,rightnode.left);
    }


    /**
     * 将二叉搜索树转换成有序的双向链表
     */
    TreeNode prev=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return null;
        TreeNode head=pRootOfTree;
        while(head.left!=null){
            head=head.left;
        }
        //head位置就是头结点位置
        ConvertChild(pRootOfTree);
        return head;
    }
    //进行中序遍历移动指针*--通过中序遍历确保得出的链表是有序的
    public void ConvertChild(TreeNode root){
        if(root==null) return;
        ConvertChild(root.left);//先处理左边
        //然后处理根
        root.left=prev;
        if(prev!=null) prev.right=root;
        //最后处理右边
        prev=root;
        ConvertChild(root.right);
    }

    /**
     * 将输入的前序遍历得到的字符串构建成二叉树--然后中序遍历
     */
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    public  class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            // 注意 hasNext 和 hasNextLine 的区别
            while (in.hasNextInt()) { // 注意 while 处理多个 case
                String str=in.next();
                TreeNode root=createTree(str);
                //中序遍历二叉树
                inOrderTree(root);
            }
        }
        //创建二叉树---递归创建
        public static int i=0;
        public static TreeNode createTree(String str){
            char ch=str.charAt(i);
            TreeNode root=null;
            if(ch!='#'){//不能拿#来创建树
                //先创建根树
                TreeNode root=new TreeNode(ch);
                //创建左树
                i++;
                root.left=createTree(str);
                //创建右树
                i++;
                root.right=createTree(str);
            }else i++;
            return root;
        }
        public static void inOrderTree(TreeNode root){
            if(root==null) return;
            inOrderTree(root.left);
            System.out.println(root.val);
            inOrderTree(root.right);
        }
    }

    /**
     * 层序遍历
     * o(n)
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        //借助队列完成二叉树的层序遍历
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null) return ret;
        Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){//每一个while循环就是遍历了一层
            int sz=q.size();//标记好这一层有多少个元素待会可以指定数量出队防止少出多出
            List<Integer> tmp=new ArrayList<>();//当前容器存储当前层的结果
            while(sz-->0){//一次循环出一个元素也就是遍历到该层的一个元素
                TreeNode t=q.poll();
               // tmp.add(t.val);
                if(t.left!=null) q.add(t.left);
                if(t.right!=null) q.add(t.right);
            }
            //tmp当中存的就是当前层的遍历结果
            ret.add(tmp);
        }
        return ret;
    }

    // 判断一棵树是不是完全二叉树

    /**
     * 思路:层序遍历二叉树，遇到第一个 null 节点后，后续所有节点必须为 null。
     * 如果违反，则不是完全二叉树。
     * @param root
     * @return
     */
    public boolean isCompleteTree(TreeNode root){
        if(root==null) return true;
        Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        boolean mark=false;
        while(!q.isEmpty()){
            TreeNode node=q.poll();
            if(node==null){
                mark=true;
            }
             else{
                 //每次遍历到一个不为空的位置是需要先去判断下前面是否已经出现过null了
                 if(mark){
                     //进来就说明前面已经出现过null了,然而你这里后续又存在一个不为空的位置--那么就不是完全二叉树了
                     return  false;
                 }
                q.add(node.left);
                q.add(node.right);
            }
        }
        return true;
    }

    /**
     * 求两节点的最近公共祖先----递归方式实现
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //递归判断每个节点是否是pq 是就返回该位置 -----根据返回的位置分论讨论的出结果
        if(root==null||root==p||root==q){
            return root;//只要pq在同一棵树,只要其中一个在该树根,那么就是树根
        }
        //递归终止条件---判断根是不是
        //从左边找
        TreeNode left =lowestCommonAncestor(root.left,p,q);
        //从右边找
        TreeNode right =lowestCommonAncestor(root.right,p,q);
        //根据返回结果分情况讨论
        if(left!=null&&right!=null) return root;//说明左右两边都有--则为root
        //全部分布在根树的某一侧11
        return left!=null ? left : right;
    }

    /**
     * 使用hash表来写--没有递归好
     * t---->o(n)
     * k--->o(n)
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        //先将从根到p q的链路径存到哈希表当中----找到p q位置之前一直记录当前节点的父亲节点
        Map<TreeNode,TreeNode> map=new HashMap<>();
        map.put(root,null);
        //采用层序遍历方式寻找
        Queue<TreeNode> qe=new LinkedList<>();
        qe.add(root);
        //只要hash表没有pq就一直找
        while(!map.containsKey(p)||!map.containsKey(q)){
            TreeNode node=qe.poll();
            if(node.left!=null) {
                qe.add(node.left);
                map.put(node.left,node);
            }
            if(node.right!=null)
            {
                qe.add(node.right);
                map.put(node.right,node);
            }
        }
        //移动往回移动q并记录q的路径---
        Set<TreeNode> set=new HashSet<>();
        while(q!=null){
            set.add(q);
            q=map.get(q);
        }
        while(!set.contains(p))
        {
            p=map.get(p);
        }
        return p;
    }

    /**
     * 知道前序 中序遍历结果构建二叉树
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    int preIndex=0;
    public TreeNode  buildTreeChild(int[] preorder, int[] inorder,int si,int ei){
        //终止条件
        TreeNode root=null;
        if(ei<si) return null;
        //创建根树
        //root=new TreeNode(preorder[preIndex]);
        int ri=findval(inorder,si,ei,preorder[preIndex]);
        preIndex++;
        //创建左子树
        root.left=buildTreeChild(preorder,inorder,si,ri-1);
        //创建右子树
        root.right=buildTreeChild(preorder,inorder,ri+1,ei);
        return root;
    }
    public int findval(int[] inorder,int si,int ei,int val){
        for(int i=si;i<=ei;i++){
            if(inorder[i]==val) return i;
        }
        return -1;
    }

    /**
     * 根据后序和中序遍历的结果构建二叉树
     */
   /* int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex=postorder.length-1;
        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }
    public TreeNode  buildTreeChild(int[] inorder, int[] postorder,int bi,int ei){
        if(bi>ei) return null;
        TreeNode root=new TreeNode(postorder[postIndex]);
        int ri=findval(inorder,bi,ei,postorder[postIndex]);
        postIndex--;
        root.right=buildTreeChild(inorder,postorder,ri+1,ei);
        root.left=buildTreeChild(inorder,postorder,bi,ri-1);
        return root;
    }
    public int findval(int[] inorder,int si,int ei,int val){
        for(int i=si;i<=ei;i++){
            if(inorder[i]==val) return i;
        }
        return -1;
    }

    */
    //使用哈希表优化findval--消耗空间换时间---因为这个地方有通过值来找下标这样的操作,而值和下标是存在一定的映射关心的
    /*int postIndex;
    Map<Integer,Integer> hash;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        hash=new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            hash.put(inorder[i],i);
        }
        postIndex=postorder.length-1;
        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }
    public TreeNode  buildTreeChild(int[] inorder, int[] postorder,int bi,int ei){
        if(bi>ei) return null;
        TreeNode root=new TreeNode(postorder[postIndex]);
        int ri=hash.get(postorder[postIndex]);
        postIndex--;
        root.right=buildTreeChild(inorder,postorder,ri+1,ei);
        root.left=buildTreeChild(inorder,postorder,bi,ri-1);
        return root;
    }

     */

    /**
     * 将二叉树转换成字符串---恶心得要死
     * @param root
     * @return
     */
    public String tree2str(TreeNode root) {
        if(root==null) return "";
        //先处理根--对于根的处理没有任何条件--直接拼接即可
        String ret=String.valueOf(root.val);
        //处理左边---这个是有条件的---只要你这个根的左右子树别同时为空即可
        if(root.left!=null||root.right!=null){
            //处理操作
            ret+="("+tree2str(root.left)+")";
        }
        //处理右边---条件--->只要右边不为空就可以来处理
        if(root.right!=null){
            ret+="("+tree2str(root.right)+")";
        }
        return ret;
    }

    /*
    前序遍历非递归实现
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret=new ArrayList<>();
         Stack<TreeNode> stack=new Stack<>();
         stack.push(root);
        if(root==null) return ret;
        while(!stack.isEmpty()){
            //循环出入栈操作直到栈为空
            TreeNode node=stack.pop();
            ret.add(node.val);
            //这里注意一定是先入右边在入左边--因为后进先出--达到先左再右的前序效果
            if(node.right!=null) stack.push(node.right);
            if(node.left!=null) stack.push(node.left);
        }
        return ret;
    }

     */


    /*
    中序遍历非递归实现
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret=new LinkedList<>();
        Stack<TreeNode> stack=new Stack<>();
        while(!stack.isEmpty()||root!=null){
            //确保栈顶是最左边的元素
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            //栈顶一定是也可以出的了
            TreeNode node=stack.pop();
            ret.add(node.val);
            root=node.right;
        }
        return ret;
    }

     */

    /*
    非递归方式实现后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        //思路:双栈法---一个栈存根节点---从主栈弹出节点入到辅助栈,同时将该节点的左右孩子节点入到主栈
        //循环上述操作直到主栈为空.顺序pop辅助栈即可的到结果
        Stack<TreeNode> stack1=new Stack<>();//主栈
        Stack<TreeNode> stack2=new Stack<>();//辅助栈
        stack1.push(root);
        List<Integer> ret=new ArrayList<>();
        if(root==null) return ret;
        while(!stack1.isEmpty()){
            TreeNode node=stack1.pop();
            stack2.push(node);
            if(node.left!=null) stack1.push(node.left);
            if(node.right!=null) stack1.push(node.right);
        }
        //顺序的pop栈2即可
        while(!stack2.isEmpty()){
            ret.add(stack2.pop().val);
        }
        return ret;
    }
     */










}
